LeetCode——不同路径

NO.62 不同路径中等

思路一：动态规划 只能向下或向右，就是无法后退或者绕路且到达终点的步数是确定的。

dp[][]数组的含义：dp[i][j]就是到到i行j列的位置有多少种走法。

初始化：dp[0][0]~dp[0][n-1]即第一列和dp[0][0]~dp[0][n-1]即第一行因为只有向下或向右移动，所以都只有1走法可以到达。

状态转移：除了第一行、第一列，dp[i][j]=dp[i-1][j]+dp[i][j-1]，还是因为只能向下或向右移动，所以dp[i][j]的一定是从其上面的[i][j-1]或左面的[i-1][j]移动而来。

public int uniquePaths(int m, int n) {
    int[][] dp=new int[m][n];
    //初始化
    for (int i = 0; i < m; i++) dp[i][0]=1;
    for (int j = 0; j < n; j++) dp[0][j]=1;
    //状态转移
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

时间复杂度：O(m*n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github

NO.62 不同路径 中等

NO.62 不同路径中等